//
//  LinkList.swift
//  LinkListS
//
//  Created by David on 2017/3/6.
//  Copyright © 2017年 David. All rights reserved.
//

import Foundation

prefix func ~(s: AnyObject) -> ObjectIdentifier{
    return ObjectIdentifier(s)
}

class LinkNode{
    var data: Any?
    var next: LinkNode?
    init(data: Any?, next: LinkNode?){
        self.data = data
        self.next = next
    }
    init(data: Any?) {
        self.data = data
    }
    
}

class LinkList: NSObject {
    
    private var _first: LinkNode?
    private var _last: LinkNode?
    private var _count = 0
    
    override init() {
        super.init()
        _first = LinkNode(data: nil)
        _last = _first
    }
    
    
    var count: Int{
        return _count
    }
    
    var isEmpty: Bool{
        return count == 0
    }
    
    var first: Any?{
        return _first?.next?.data
    }

    var last: Any?{
        return _last?.data
    }
    
    func append(_ element: Any?){
        let node = LinkNode(data: element, next: nil)
        _last?.next = node
        _last = node
        
        _count += 1
    }
    
    func insert(_ element: Any?, at: Int){
        if at < 0 || at > _count {
            print("LinkList: Index out of range.")
            return
        }
        
        var i = at
        var p = _first
        while i > 0 {
            p = p?.next
            i -= 1
        }
        let node = LinkNode(data: element, next: p?.next)
        p?.next = node
        _count += 1
    }
    
    func remove(at: Int){
        if at < 0 || at >= _count {
            print("LinkList: Index out of range.")
            return
        }
        
        var i = at
        var p = _first
        while i > 0 {
            p = p?.next
            i -= 1
        }
//        var node = p?.next
        p?.next = p?.next?.next
//        node = nil
        _count -= 1
    }
    
    func removeAll(){
        _first?.next = nil
        _last = nil
        _count = 0
//        while p != _last {
//            var q = p?.next
//            p = nil
//            
//        }
    }
    
    //让print函数打印出所哟元素
    override var description: String{
        var des = "["
        for i in 0..<count{
            des += "\(self[i] ?? "nil")"
            des += i == count - 1 ? "" : ", "
        }
        des += "]"
        return des
    }
    
    //可以这样用 `对象名`[Int]
    subscript(at: Int) -> Any?{
        if at < 0 || at >= _count {
            print("LinkList: Index out of range.")
            return nil
        }
        var i = at
        var p = _first?.next
        while i > 0 {
            p = p?.next
            i -= 1
        }
        return p?.data
    }
    
    func getNode(at: Int) ->LinkNode? {
        if at < 0 || at >= _count {
            print("LinkList: Index out of range.")
            return nil
        }
        var i = at
        var p = _first?.next
        while i > 0 {
            p = p?.next
            i -= 1
        }
        return p
    }
    
    func createLoop(to: Int){
        _last?.next = getNode(at: to)
        
    }
    
    var hasLoop: Bool{
        var fast = _first?.next
        var slow = _first
        
        if fast == nil || slow == nil{
            return false
        }
        
//        while ObjectIdentifier(fast!) != ObjectIdentifier(slow!) {
        while ~fast! != ~slow! {
            fast = fast?.next?.next
            slow = slow?.next
            if fast == nil || slow == nil{
                return false
            }
        }
        return true
    }
    
}
